Market adoption of wireless LAN (WLAN) technology has exploded, as users from a wide range of backgrounds and vertical industries have brought this technology into their homes, offices, and increasingly into the public air space. This inflection point has highlighted not only the limitations of earlier-generation systems, but the changing role WLAN technology now plays in people's work and lifestyles, across the globe. Indeed, WLANs are rapidly changing from convenience networks to business-critical networks. Increasingly users are depending on WLANs to improve the timeliness and productivity of their communications and applications, and in doing so, require greater visibility, security, management, and performance from their network.
The rapid proliferation of lightweight, portable computing devices and high-speed WLANs has enabled users to remain connected to various network resources, while roaming throughout a building or other physical location. The mobility afforded by WLANs has generated a lot of interest in applications and services that are a function of a mobile user's physical location. Examples of such applications include: printing a document on the nearest printer, locating a mobile user, displaying a map of the immediate surroundings, and guiding a user inside a building. The required or desired granularity of location information varies from one application to another. Indeed, the accuracy required by an application that selects the nearest network printer, or locates a rogue access point, often requires the ability to determine in what room a mobile station is located. Accordingly, much effort has been dedicated to improving the accuracy of wireless node location mechanisms.
The use of radio signals to estimate the location of a wireless device or node is known. For example, a Global Positioning System (GPS) receiver obtains location information by triangulating its position relative to four satellites that transmit radio signals. The GPS receiver estimates the distance between each satellite based on the time it takes for the radio signals to travel from the satellite to the receiver (i.e., Time Difference Of Arrival (TDOA) calculations). Signal propagation time is assessed by determining the time shift required to synchronize the pseudo-random signal transmitted by the satellite and the signal received at the GPS receiver. Although triangulation only requires distance measurements from three points, an additional distance measurement from a fourth satellite is used for error correction.
The distance between a wireless transmitter and a receiver can also be estimated based on the strength of the received signal, or more accurately the observed attenuation of the radio signal. Signal attenuation refers to the weakening of a signal over its path of travel due to various factors like terrain, obstructions and environmental conditions. Generally speaking, the magnitude or power of a radio signal weakens as it travels from its source. The attenuation undergone by an electromagnetic wave in transit between a transmitter and a receiver is referred to as path loss. Path loss may be due to many effects such as free-space loss, refraction, reflection, and absorption.
In business enterprise environments, most location-tracking systems are based on RF triangulation or RF fingerprinting techniques. RF triangulation calculates a mobile station's location based upon the detected signal strength of nearby access points (APs). It assumes that signal strength is a factor of proximity, which is true in certain RF environments. However, the multipath phenomenon encountered in indoor RF environments, which include walls, windows, and other RF obstructions, does present certain difficulties for location systems using triangulation, since reflection and absorption of RF signals affects the correlation between signal strength and proximity. RF fingerprinting compares a mobile station's, or access point's, view of the RF environment (i.e., the strength of signals transmitted by the infrastructure access points, or the mobile station) with a database that contains an RF physical model of the coverage area. This database is typically populated by either an extensive site survey, a RF prediction model of the coverage area, and other statistical techniques. For example, Bahl et al., “A Software System for Locating Mobile Users: Design, Evaluation, and Lessons,” http://research.microsoft.com/˜bahl/Papers/Pdf/radar.pdf, describes an RF location system (the RADAR system) in a WLAN environment, that allows a mobile station to track its own location relative to access points in a WLAN environment.
The RADAR system relies on a so-called Radio Map, which is a database of locations in a building and the signal strength of the beacon packets emanating from the access points as observed, or estimated, at those locations. For example, an entry in the Radio Map may look like (x, y, z, ssi (i=1 . . . n)), where (x, y, z) are the physical coordinates of the location where the signal is recorded, and ssi is the signal strength of the beacon signal emanating from the ith access point. According to Bahl et al., Radio Maps may be empirically created based on heuristic evaluations of the signals transmitted by the infrastructure radios at various locations, or mathematically created using a mathematical model of indoor RF signal propagation. To locate the position of the mobile user in real-time, the mobile station measures the signal strength of each of access points within range. It then searches all locations in the Radio Map database against the detected signal strengths to find the location with the best match. Bahl et al. also describe averaging the detected signal strength samples, and using a tracking history-based algorithm, to improve the accuracy of the location estimate.
Computing the location in the Radio Map of the RADAR system which best fits the signal strength observed by the mobile station can be quite computationally intensive, especially as the boundaries of the RF environment and/or the granularity of the location coordinates in the Radio Map increase. The client application in the RADAR system searches the entire Radio Map for the best fitting location coordinates. While this circumstance does not represent a substantial limitation for the RADAR system, which involved a limited number of access points and location bins, this un-optimized search algorithm does not scale to large wireless network deployments, which may include hundreds to thousands of access points and hundreds of location bins in the coverage maps for each access point. In other words, the number of computations required to check each possible location as the best match grows with the size, and number of access points, within the RF environment. Indeed, in large wireless network deployments, as discussed more fully below, the location of a wireless node could involve checking millions to tens of millions of possible locations to find the best matching location. Moreover, the size of the database required to support wireless node location, according to the RADAR system, can become quite large. Accordingly, this un-optimized search algorithm can place a significant burden on the processing resources associated with a wireless node location system, especially infrastructure-based systems that perform other functions, such as providing wireless network access to the mobile stations.
In light of the foregoing, a need in the art exists for methods, apparatuses and systems that optimize the search for best fitting location coordinates in wireless node location mechanisms. Embodiments of the present invention substantially fulfill this need.